﻿using System;
using System.Collections.Generic;

namespace _05_贪心与暴力递归
{
   class Program
   {
      // 走台阶问题
      static int Step(int leftStep)
      {
         if (leftStep == 0)
            return 1;
         if (leftStep < 0)
            return 0;
         return Step(leftStep - 1) + Step(leftStep - 2);
      }

      // 会议室问题
      static List<int[]> Meeting(int[][] allMeetings, int timePoint)
      {
         Array.Sort(allMeetings, new MeetingComparator());
         List<int[]> res = new List<int[]>();
         // 依次遍历所有会议
         for (int i = 0; i < allMeetings.Length; i++)
         {
            // 当前会议室空余
            if (timePoint <= allMeetings[i][0])
            {
               timePoint = allMeetings[i][1];
               res.Add(allMeetings[i]);
            }
         }

         return res;
      }

      struct MeetingComparator : IComparer<int[]>
      {
         public int Compare(int[] x, int[] y)
         {
            return x[1] - y[1];
         }
      }

      // 获得最大字典序拼接字符串
      static string ConcatString(params string[] strs)
      {
         string res = "";
         // 排序
         Array.Sort(strs, new ConcatStringComparator());
         // 拼接
         for (int i = 0; i < strs.Length; i++)
         {
            res += strs[i];
         }

         return res;
      }

      struct ConcatStringComparator : IComparer<string>
      {
         public int Compare(string x, string y)
         {
            return -(x + y).CompareTo(y + x);
         }
      }

      /**
       * 游戏经验与任务问题：
       *    输入tasks[]   needExp完成任务需要的经验 getExp完成任务得到的经验
       *    输入exp    初始经验
       *    返回最大获得的经验
       */
      static int MaxExp(Task[] tasks, int exp)
      {
         SortedSet<Task> s = new SortedSet<Task>(new NeedExpComparator());
         foreach (var item in tasks)
            s.Add(item);
         SortedSet<Task> available = new SortedSet<Task>(new GetExpComparator());

         while (s.Count != 0)
         {
            // 添加所有可选择的任务
            while (s.Count != 0 && exp <= s.Min.needExp)
            {
               Task availableTask = s.Min;
               available.Add(availableTask);
               s.Remove(availableTask);
            }
            // 所有可选择的任务中选给经验最多的
            exp += available.Max.getExp;
            available.Remove(available.Max);
            if (s.Count == 0 && available.Count == 0)
               break;
         }

         return exp;
      }

      struct Task
      {
         public int needExp;
         public int getExp;

         public Task(int needExp, int getExp)
         {
            this.needExp = needExp;
            this.getExp = getExp;
         }
      }

      struct NeedExpComparator : IComparer<Task>
      {
         public int Compare(Task x, Task y)
         {
            return x.needExp - y.needExp;
         }
      }

      struct GetExpComparator : IComparer<Task>
      {
         public int Compare(Task x, Task y)
         {
            return x.getExp - y.getExp;
         }
      }

      static void Main(string[] args)
      {
         //Console.WriteLine(Step(10));
         //int[][] meetings = new int[5][]
         //{
         //   new int[]{6, 7},
         //   new int[]{9, 14},
         //   new int[]{10, 12},
         //   new int[]{13, 19},
         //   new int[]{15, 19},
         //};
         //Console.WriteLine(Meeting(meetings, 6));

         //Console.WriteLine(ConcatString("ABCD", "AASX", "HELLO", "WORLD", "BCADS"));

         Task[] tasks = new Task[]
         {
            new Task(1, 4),
            new Task(3, 5),
            new Task(4, 3),
            new Task(4, 6),
         };
         MaxExp(tasks, 1);
      }
   }
}
